package main

// https://www.zhihu.com/people/xu-xian-sheng-80-10/posts?page=2

import "fmt"

// 208: trie leetcode
//  前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
//输入
//["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
//[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
//输出
//[null, null, true, false, true, null, true]

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func Constructor() Trie {
	return Trie{}
}

func (this *Trie) Insert(word string) {
	node := this
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (this *Trie) Search(word string) bool {
	node := this.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
	return this.SearchPrefix(prefix) != nil
}

func (this *Trie) SearchPrefix(prefix string) *Trie {
	node := this
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return nil
		}
		node = node.children[ch]
	}
	return node
}

// project Trie
// 查询， 前缀匹配，前缀统计，插入， 删除
type Trie_ struct {
}

// radix tree: 前缀树 trie 的升级版本——压缩前缀树/基数树 radix tree.
// 插入 查询 前缀匹配， 前缀统计 删除
type radixNode struct {
	path     string
	fullPath string
	indices  string
	children []*radixNode
	end      bool
	passCnt  int
}

// 使用 trie 作为经纬度哈希编码存储结构的 geohash 算法，以及
// 使用 radix tree 作为路由存储结构的 gin 框架.
func main() {
	fmt.Print("start ... ")
	fn := []string{"Trie", "insert", "search", "search", "startsWith", "insert", "search"}
	el := [][]string{{}, {"apple"}, {"apple"}, {"app"}, {"app"}, {"app"}, {"app"}}
	for _, x := range fn {
		fmt.Println(x)
	}
	for _, x := range el {
		if len(x) > 0 {
			fmt.Println(x[0])
		}
	}

}
